package leetcodev1.数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode90 {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        helper(nums, 0, new ArrayList<>(), visited, ret);
        return ret;
    }

    private void helper(int[] nums, int index, List<Integer> router, boolean[] visited, List<List<Integer>> ret) {
        if (index == nums.length) {
            ret.add(new ArrayList<>(router));
            return;
        }

        //选择该元素(自己是第一个元素 或 前一个相同元素已经被选过了)
        if (index == 0 || nums[index] != nums[index - 1] || visited[index - 1]) {
            router.add(nums[index]);
            visited[index] = true;
            helper(nums, index + 1, router, visited, ret);
            //回溯状态
            router.remove(router.size() - 1);
            visited[index] = false;
        }

        //不选该元素
        helper(nums, index + 1, router, visited, ret);
    }

    //枚举所有结果
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsetsWithDup1(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            boolean flag = true;
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
                        flag = false;
                        break;
                    }
                    t.add(nums[i]);
                }
            }
            if (flag) {
                ans.add(new ArrayList<Integer>(t));
            }
        }
        return ans;
    }

    public List<List<Integer>> subsetsWithDup2(int[] nums) {
        Arrays.sort(nums);
        dfs(false, 0, nums);
        return ans;
    }

    //牛逼
    //记录一下上次相同的元素是否选择即可
    public void dfs(boolean choosePre, int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        dfs(false, cur + 1, nums);
        if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
            return;
        }
        t.add(nums[cur]);
        dfs(true, cur + 1, nums);
        t.remove(t.size() - 1);
    }

}
